import java.util.Deque;
import java.util.LinkedList;

/**
 * Created by zhourh on 2018/9/18.
 *
 * 给定一个非负整数数组 A，返回一个由 A 的所有偶数元素组成的数组，后面跟 A 的所有奇数元素。

 你可以返回满足此条件的任何数组作为答案。

 双端队列
 */
public class SortArrayByParity {

    public static void main(String[] args) {
        Printer.printIntArray(new SortArrayByParity().sortArrayByParity(new int[]{3,1,2,4}));
    }

    public int[] sortArrayByParity(int[] A) {
        Deque<Integer> deque = new LinkedList<>();
        if (A == null || A.length == 0) {
            return A;
        }

        for (int a : A) {
            if ((a & 0x01) == 0) {
                deque.addFirst(a);
            } else {
                deque.addLast(a);
            }
        }

        int[] ans = new int[A.length];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = deque.pollFirst();
        }

        return ans;
    }
}
